package com.example.interview.algorithm;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

/**
 * 在字符串中找出第一个只出现一次的字符
 * @Description: TODO
 * @author gaobing
 * @date 2018年10月16日 下午1:14:40
 * 思路：由于题目与字符出现的次数相关， 我们是不是可以统计每个字符在该字符串中出现的次数？要达到这个目的，我们需要一个数据容器来存放每个字符的出现次数。
 * 在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成二个数字。在常用的数据容器中， 哈希表正是这个用途。 
　　为了解决这个问题，我们可以定义哈希表的键（Key）是字符， 而值(Value ）是该字符出现的次数。同时我们还需要从头开始扫描字符串两次。
        第一次扫描字符串时，每扫描到一个字符就在哈希表的对应项中把次数加1 。接下来第二次扫描时， 每扫描到一个字符就能从哈希表中得到该字符出现的次数。这样第一个只出现一次的字符就是符合要求的输出。 
　　第一次扫描时，在哈希表中更新一个字符出现的次数的时间是O(n) 。如果字符串长度为n， 那么第一次扫描的时间复杂度是O(n)。
        第二次扫描时，同样0(1)能读出一个字符出现的次数，所以时间复杂度仍然是O(n)。这样算起来，总的时间复杂度是O(n)。
   */
public class Test35StringFirst {

	/**
	 * 
	 * @param s
	 * @return
	 */
	public static char firstNotRepeatingChar(String s) {
		if (s==null||s.length()<1) {
			throw new IllegalArgumentException("arg should not be null or empty");
		}
		/**
		 * 1、一般情况下，我们用的最多的是HashMap。HashMap里面存入的键值对在取出的时候是随机的，它根据键的HashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。
		 * 在Map 中插入、删除和定位元素，HashMap 是最好的选择。
　　		   2、TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。
　		   3、LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现,它还可以按读取顺序来排列，像连接池中可以应用。
		 */
		Map<Character, Integer> map = new LinkedHashMap<>();
		char c;
		for(int i=0;i<s.length();i++) {
			  c=s.charAt(i);
			  if (map.containsKey(c)) {
				map.put(c, -1);
			}else {
				map.put(c, i);
			}
		} 
		 
		//记录只出现一次的字符
		char result='\0';
		//找最小索引对应的字符
		for(Map.Entry<Character, Integer> entry:map.entrySet()) {
			if (entry.getValue()>=0) { 
				result=entry.getKey();
				break;
			}
		}
		return result;
	}
	
	public static void main(String[] args) {
		System.out.println(firstNotRepeatingChar("googl")); // l
		System.out.println(firstNotRepeatingChar("google")); // l
        System.out.println(firstNotRepeatingChar("aabccdbd")); // '\0'
        System.out.println(firstNotRepeatingChar("abcdefg")); // a
        System.out.println(firstNotRepeatingChar("gfedgba")); // g
        System.out.println(firstNotRepeatingChar("zgfedcba")); // g
 	}
}
